/**
//输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。 
//
// 
//
// 参考以下这颗二叉搜索树： 
//
//      5
//    / \
//   2   6
//  / \
// 1   3 
//
// 示例 1： 
//
// 输入: [1,6,3,2,5]
//输出: false 
//
// 示例 2： 
//
// 输入: [1,3,2,6,5]
//输出: true 
//
// 
//
// 提示： 
//
// 
// 数组长度 <= 1000 
// 
// Related Topics 栈 树 二叉搜索树 递归 二叉树 单调栈 👍 382 👎 0

*/

package com.xixi.dataStructure.tree.binaryTree;
public class ID_Offer_33_ErChaSouSuoShuDeHouXuBianLiXuLieLcof {
public static void main(String[] args) {
Solution solution = new ID_Offer_33_ErChaSouSuoShuDeHouXuBianLiXuLieLcof().new Solution();
}


//leetcode submit region begin(Prohibit modification and deletion)
class Solution {

    boolean res = true;
    public boolean verifyPostorder(int[] postorder) {

        res = judgeChild(postorder, 0, postorder.length -1 );
        return  res;
    }

    public boolean judgeChild(int[] postorder, int pFrom, int pTo ) {

        if(pFrom >= pTo) return res;

        //先通过根节点，找到L < root < R 区别左右子树的位置
        //如果都 小于 root，说明没有右子树
        //如果都 大于root， 说明没有左子树
        int rootVal = postorder[pTo];
        int leftIndex = pTo - 1; //从第二位开始找，也就是从子树开始找，当碰到第一个小于rootVal的值的时候，就假设是左右子树分界， 既是左数根节点
        //一直找到最后一位， 最后依次，rootIndex会变为-1
        while( leftIndex >= pFrom ){
            if(postorder[leftIndex] < rootVal ){ //找到左子树根节点的下标
                break;
            }
            --leftIndex;
        }

        if(leftIndex == (pTo -1)){ //一开始就碰到小于的，假设只有左子树
            for(int lChild = leftIndex -1; lChild >= pFrom; --lChild){ //判断左子树是否都小于rootVal
                if(postorder[lChild] >= rootVal){ //如果有大于等于， 直接返回false
                    res = false;
                    return res;
                }
            }
            judgeChild(postorder, pFrom, pTo -1); //继续判断子树是否也为查找树
        }else if(leftIndex > pFrom-1 && leftIndex < (pTo -1)){ //假设有左子树，也有右子树
            //因为leftIndex后面已经判断过了，所以只用判断leftIndex以前的是否符合左子树
            for(int lChild = leftIndex -1; lChild >= pFrom; --lChild){ //判断左子树是否都小于rootVal
                if(postorder[lChild] >= rootVal){ //如果有大于等于， 直接返回false
                    res = false;
                    return res;
                }
            }
            res=judgeChild(postorder, pFrom, leftIndex); //继续判断左子树是否也为查找树
            if(res){ //剪枝
                res = judgeChild(postorder, leftIndex+1, pTo -1); //继续判断右子树是否也为查找树
            }

        }else if(leftIndex == pFrom-1){ //只有右子树
            res = judgeChild(postorder, pFrom, pTo-1); //继续判断子树是否也为正常
        }

        //时间复杂度大约是O(n的方)
        return res;
    }

}
//leetcode submit region end(Prohibit modification and deletion)




}